package leecode;

import org.apache.kafka.common.protocol.types.Field;

import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * 回文数
 *
 * @author qingyan 2021-11-26
 */
public class Question5 {

    /**
     * 暴力查找
     * @param s
     * @return
     */
    public String longestPalindrome_1(String s) {
        int length = s.length();

        if (length < 2) {
            return String.valueOf(s.charAt(0));
        }

        String string = "";

        for (int i = 0; i < length - 1; i++) {

            char c = s.charAt(i);

            for (int j = i + 1; j < length; j++) {
                if (j - i + 1 <= string.length()) {
                    continue;
                }

                int k = (j - i) / 2;

                do {
                    if (s.charAt(i + k) == s.charAt(j - k)) {
                    } else {
                        break;
                    }
                } while (--k >= 0);

                if (k < 0) {
                    if (string.length() < j - i + 1) {
                        string = s.substring(i, j + 1);
                    }
                }

            }


        }

        if (string.equals("")) {
            string = String.valueOf(s.charAt(0));
        }

        return string;

    }

    // 先进先出栈
    public String longestPalindrome_2(String s) {

        int length = s.length();

        if (length < 2) {
            return String.valueOf(s.charAt(0));
        }

        LinkedList<Character> list = null;

        String str = "";

        for (int i = 0; i < length; i++) {
            list = new LinkedList<>();
            list.add(s.charAt(i));
            for (int j = i + 1; j < length; j++) {

                char c = s.charAt(j);

                if ((j - i) == list.size()) {
                    if (c != list.getLast()) {
                        if (j - i > 1 && list.get(j - i - 2) == c) {
                            list.removeLast();
                            list.removeLast();
                        } else {
                            list.add(c);
                        }
                    } else {
                        list.removeLast();
                    }
                } else if (c == list.getLast()) {
                    list.removeLast();
                } else {
                    break;
                }

                if (list.isEmpty()) {

                    if (j + 1 - i > str.length()) {
                        str = s.substring(i, j + 1);
                    }
                    break;
                }

            }
        }

        if (str.equals("")) {
            str = String.valueOf(s.charAt(0));
        }

        return str;
    }

    // 递归
    private void recursion(int length, int index, LinkedList<Character> list, char c) {


    }

    public static void main(String[] args) {
        Question5 question5 = new Question5();
        System.out.println(question5.longestPalindrome_2("cbbd"));
    }
}
